package 牛客.链表;

import 剑指offer.ListNode;

public class BM4合并两个排序的链表 {
    public ListNode Merge(ListNode list1, ListNode list2) {
        //递归
        if (list1==null) {
            return list2;
        }else if (list2==null) {
            return list1;
        }else if (list1.val < list2.val) {
            list1.next=Merge(list1.next,list2);
            return list1;
        }else {
            list2.next=Merge(list1,list2.next);
            return list2;
        }
    }

    public ListNode Merge1(ListNode list1, ListNode list2) {
        ListNode dummyNode=new ListNode(-1);
        ListNode p1=list1;
        ListNode p2=list2;

        ListNode cur=dummyNode;
        while (p1!=null && p2!=null) {
            if (p1.val<p2.val) {
                cur.next=p1;
                p1=p1.next;
            }else {
               cur.next=p2;
               p2 = p2.next;
            }
            cur=cur.next;
        }

        if (p1==null) {
            cur.next=p2;
        }
        if (p2==null) {
            cur.next=p1;
        }

        return dummyNode.next;

    }

}
